package com.breeze.leetcode;

/**
 * 82. 删除排序链表中的重复元素 II
 * https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii/
 * <p>
 * 给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。
 */
public class LeetCode82 {
    static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    static class Solution {
        public ListNode deleteDuplicates(ListNode head) {
            // 因为当前节点有可能不符合要求需要删除，故增加哑节点
            ListNode dummy = new ListNode(-1, head);
            ListNode temp = dummy;
            while (temp != null && temp.next != null) {
                // 直接从下个节点开始判断
                ListNode node = temp.next;
                boolean duplicated = false;
                // 下个节点如果和下下个节点的值相同，则使其指向下下个节点，直到不同时退出，此时node就指向重复节点的最后一个
                while (node.next != null && node.val == node.next.val) {
                    node = node.next;
                    duplicated = true;
                }
                // 包含重复节点，则当前节点直接指向最后一个重复节点的下个节点
                if (duplicated) {
                    temp.next = node.next;
                } else {
                    // 不重复更新temp位下一个即可
                    temp = temp.next;
                }
            }
            return dummy.next;
        }
    }

    public static void main(String[] args) {
        ListNode listNode3 = new ListNode(3, null);
        ListNode listNode2 = new ListNode(2, listNode3);
        ListNode listNode1 = new ListNode(1, listNode2);
        ListNode listNode = new ListNode(1, listNode1);
        Solution solution = new Solution();
        ListNode listNode4 = solution.deleteDuplicates(listNode);
        while (listNode4 != null) {
            System.out.println(listNode4.val);
            listNode4 = listNode4.next;
        }
    }
}
